"""
二分查找，也叫折半查找
左右指针，比较 中间的数 与 要查找的数 的大小
前提是列表已经 从小到大 排好序了

时间复杂度O(logn)
"""


def binary_search(li, value):
    left, right = 0, len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == value:
            return mid
        elif li[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    else:
        return None


if __name__ == '__main__':
    li = [1, 2, 3, 4, 5, 6, 7, 8]
    print(binary_search(li, 6))


